[BAEKJOON] 19236. 청소년 상어
Posted on
문제 :
아기 상어가 성장해 청소년 상어가 되었다.
4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.
오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.
물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.
물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.
⇒ 자세한 그림 참조 : 링크
입력 :
첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.
출력 :
상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.
풀이 :
오늘 또 한번 내가 구현 문제에 약하다는 것을 절실히 느꼈다.
우선 아기 상어를 얼마 전에 풀어본 기억이 났는데 청소년 상어는 확실히 더 어려워진 느낌이 풍겼다. 내가 구현에 약한 이유는 구현 문제를 설계할 때 차근차근 시작하지 못하는 점이 큰 것 같다. 이번 문제에서도 설계과정이 확실치 않았던 것이 긴 시간이 걸린 이유인 것 같다.
우선 문제는 순서가 있고 그 순서에 따라 구현하면 테스트를 충족시킬 수 있었다.
- 상어가 먹을 수 있는 인덱스를 재귀 함수에 매개변수로 제공한다.
- 해당 인덱스의 물고기를 상어가 먹는다. 상어가 먹은 자리는 -2로 표시한다.
- 그 후, 남은 물고기들을 오름차순 번호대로 자리를 이동시켜 준다. ⇒ 이 때 주의할 점은 기존 물고기들의 위치가 저장된 배열에 지속적으로 덮어씌우면서 자리를 이동시켜주어야 한다. 한꺼번에 이동하는 방식이 아니라 순서가 정해져서 이동하기 때문에 절대로 다른 배열에 이동한 곳을 기록하는 방식을 사용하면 안된다. (내가 이렇게 풀다가 허무하게 시간을 버림…)
- 모든 물고기를 이동시킨 후에는 상어가 위치한 곳에서 이동방향대로 움직여서 먹을 수 있는 물고기들을 확인한다. 확인된 물고기들의 위치는 다시금 재귀함수의 인덱스로 넣어 함수를 실행시킨다. ⇒ 나는 이 과정에서 모든 경로를 탐색하는 완전탐색 방식을 사용함.
코드 :
코드 보기/접기
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#define pii pair<int, int>
#define vec vector<pii>
#define vec2 vector<vector<pii>>
using namespace std;
int di[8] = { -1, -1, 0, 1, 1, 1, 0, -1 }, dj[8] = { 0, -1, -1, -1, 0, 1, 1, 1 }, ans;
void sharkMove(vec2 map, vec fish, int x, int y, int sum) {
int i, j, count = 0, feed = map[x][y].first, dir, num, curx, cury, cmpdir, cmpx, cmpy, chnum;
sum += feed;
ans = max(ans, sum);
map[x][y] = pii(-2, map[x][y].second);
fish[feed] = pii(-1, -1);
for (i = 1; i < 17; i++) {
curx = fish[i].first; cury = fish[i].second;
if (curx == -1) continue;
dir = map[curx][cury].second;
num = map[curx][cury].first;
for (j = 0; j < 8; j++) {
cmpdir = (dir + j) % 8;
cmpx = curx + di[cmpdir]; cmpy = cury + dj[cmpdir];
if (0 <= cmpx && cmpx < 4 && 0 <= cmpy && cmpy < 4 && map[cmpx][cmpy].first != -2) {
fish[map[curx][cury].first] = pii(cmpx, cmpy);
chnum = map[cmpx][cmpy].first;
if (chnum != -1) fish[chnum] = pii(curx, cury);
map[curx][cury] = map[cmpx][cmpy];
map[cmpx][cmpy] = pii(num, cmpdir);
break;
}
}
}
map[x][y].first = -1;
dir = map[x][y].second;
while (1) {
x += di[dir]; y += dj[dir];
if (x < 0 || 4 <= x || y < 0 || 4 <= y) break;
if (map[x][y].first != -1) {
sharkMove(map, fish, x, y, sum);
}
}
}
int main() {
vec2 map; vec fish;
int num, dir, i, j;
fish.resize(17);
map.resize(4);
for (i = 0; i < 4; i++)
map[i].resize(4);
for (i = 0; i < 4; i++)
for (j = 0; j < 4; j++) {
cin >> num >> dir;
map[i][j] = pii(num, dir - 1);
fish[num] = pii(i, j);
}
sharkMove(map, fish, 0, 0, 0);
cout << ans << '\n';
return 0;
}